package LeetCode1;

/**
 * 合并K个升序链表
 * @author 是阿秋啊
 * @date 2023/03/06 15:23
 **/
public class Num23 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l,  int r) {
        if (l == r) return lists[l];
        if (l > r) return null;
        int mid = l + ((r - l) >> 1);
        return mergeTwoListSort(merge(lists,l,mid),merge(lists,mid+1,r));
    }

    private ListNode mergeTwoListSort(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode dummyHead = new ListNode(0);
        ListNode pre = dummyHead;
        while (list1 != null && list2 != null){
            if (list1.val <= list2.val){
                pre.next = list1;
                list1 = list1.next;
            }else {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return dummyHead.next;
    }
}